package pub.dsb.example.algorithm;

import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * <p>
 * https://leetcode-cn.com/problems/add-two-numbers/
 * </p>
 *
 * @author Yi
 * @version V1.0.0
 * @date 2021/1/4 9:27
 * @modificationHistory=========================逻辑或功能性重大变更记录
 * @modify By: {修改人} 2021/1/4 9:27
 * @modify reason: {方法名}:{原因}
 * ...
 * @since V1.0.0
 */
public class LC2Test {

    public static void main(String[] args) {
//        ListNode l1 = new ListNode(2);
//        l1.next = new ListNode(4);
//        l1.next.next = new ListNode(3);
//        ListNode l2 = new ListNode(5);
//        l2.next = new ListNode(6);
//        l2.next.next = new ListNode(4);
        //int[] l1Arr = new int[]{1, 9, 9, 9, 9, 9, 9, 9, 9, 9};
        //int[] l2Arr = new int[]{9};
//        int[] l1Arr = new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
//        int[] l2Arr = new int[]{5, 6, 4};
        int[] l1Arr = new int[]{9, 9, 9, 9, 9, 9, 9};
        int[] l2Arr = new int[]{9, 9, 9, 9};
        ListNode l1 = new ListNode(l1Arr[0]);
        ListNode l2 = new ListNode(l2Arr[0]);
        ListNode tmp = null;
        for (int i = 0; i < l1Arr.length; i++) {
            if (i == 0) {
                tmp = l1;
            } else {
                tmp.next = new ListNode(l1Arr[i]);
                tmp = tmp.next;
            }
        }
        for (int i = 0; i < l2Arr.length; i++) {
            if (i == 0) {
                tmp = l2;
            } else {
                tmp.next = new ListNode(l2Arr[i]);
                tmp = tmp.next;
            }
        }
        new Solution0().addTwoNumbers(l1, l2);
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution0 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> l1Value = new ArrayList<>();
        List<Integer> l2Value = new ArrayList<>();
        l1Value.add(l1.val);
        l2Value.add(l2.val);
        ListNode tmp = l1;
        ListNode result = null;
        while (Objects.nonNull(tmp.next)) {
            tmp = tmp.next;
            l1Value.add(tmp.val);
        }
        tmp = l2;
        while (Objects.nonNull(tmp.next)) {
            tmp = tmp.next;
            l2Value.add(tmp.val);
        }
        int len = l2Value.size() > l1Value.size() ? l2Value.size() : l1Value.size();
        BigInteger val = new BigInteger("0");
        for (int i = len - 1; i >= 0; i--) {
            if (l1Value.size() >= i + 1) {
                BigInteger step = new BigInteger("10").pow(i).multiply(new BigInteger(String.valueOf(l1Value.get(i))));
                val = new BigInteger(new DecimalFormat("0").format(step)).add(val);
            }
            if (l2Value.size() >= i + 1) {
                BigInteger step = new BigInteger("10").pow(i).multiply(new BigInteger(String.valueOf(l2Value.get(i))));
                val = new BigInteger(new DecimalFormat("0").format(step)).add(val);
            }
        }
        ListNode temp = null;
        String numberStr = val.toString();
        int len2 = numberStr.length();
        for (int i = 0; i < len2; i++) {
            int num = Integer.parseInt(String.valueOf(numberStr.charAt(len2 - i - 1)));
            if (result == null) {
                temp = new ListNode(num);
                result = temp;
            } else {
                temp.next = new ListNode(num);
                temp = temp.next;
            }
        }
        return result;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1), pre = dummyHead;
        int t = 0;
        // 顺序遍历链表
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                // 记录当前位数值，与L2链表同位累加，进位信息通过 `/10` 操作后续继续累加
                t += l1.val;
                // 移动 L1 链表指针
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                // 移动 L2 链表指针
                l2 = l2.next;
            }
            // 保留当前位数信息
            pre.next = new ListNode(t % 10);
            pre = pre.next;
            // 进位
            t /= 10;
        }
        return dummyHead.next;
    }
}